package easy;

import java.util.Arrays;

/**
 * 归并排序(分治思想)
 * 先对数组拆分，拆分成较小多个数组，再对小数组两两合并排序
 *
 * @author WangChenyu
 * @since 2024-04-15 09:59
 */
public class MergerSort {

    public static void main(String[] args) {
        int[] arr = {8, 5, 4, 9, 7, 3, 2, 5, 1};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 归并排序算法
     *
     * @param arr   需要排序的数组
     * @param start 开始位置
     * @param end   结束位置
     * @author WangChenyu
     * @since 10:02 2024/4/15
     **/
    public static void sort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        // 得到中间值
        int mid = start + (end - start) / 2;
        // 左右再各自排序
        sort(arr, start, mid);
        sort(arr, mid + 1, end);
        // 左右两边的有序数组合并成一个有序数组
        merger(arr, start, mid, end);
    }

    /**
     * 将数组的左右两边进行排序
     *
     * @param arr   需要排序的数组
     * @param start 开始位置（开始到中间的位置相对有序）
     * @param mid   中间的位置
     * @param end   结束位置（中间到结束的位置相对有序）
     * @author WangChenyu
     * @since 10:06 2024/4/15
     **/
    public static void merger(int[] arr, int start, int mid, int end) {
        // 创建一个临时数组用于存储排序后的数组
        int[] tmp = new int[end+1];
        int index = 0, i = start, j = mid + 1;

        while (i <= mid && j <= end) {
            tmp[index++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) {
            tmp[index++] = arr[i++];
        }

        while (j <= end) {
            tmp[index++] = arr[j++];
        }

        for (int k = 0; k < index; k++) {
            arr[start + k] = tmp[k];
        }
    }
}
